The ``Ms. Pac-Man'' game presents an interesting problem in artificial intelligence. Ghosts (enemies) move with a non-zero probability of reversing their course at any moment in time. This makes the task of predicting the behavior of a ghost at a given point in the future very challenging. Previous work has looked at various methods of rule-based control of a ``Ms. Pac-Man'' agent, methods for evolving the agent's behavior over time, or treating the ``Ms. Pac-Man'' world as a graph, and attempting to find a optimal strategy in each situation.

Our proposed method is inspired by both the evolutionary and graph-based approaches to the ``Ms. Pac-Man'' problem. We represent the game maze as graph, where nodes are made from the junctions of the maze (where ``Ms. Pac-Man'' can move in more than two directions), power pill locations, and, under some circumstances, the location of the ``Ms. Pac-Man'' agent. Edges exist between nodes where the shortest path between them does not contain another node. The weight of each edge is influenced by the presence of pills, power pills, inedible ghosts, and edible ghosts on the path between the nodes. This ``cost'' of an edge influences the decisions that are made in navigating ``Ms. Pac-Man'' around the maze.

We show that our method outperforms the rule-based methods and could be used to direct the design of more successful, evolutionary agents.
